#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<stack>
using namespace std;

class Solution{
    public:
    bool ans1(string s){
        stack<char> stk;
        if(s.size() % 2 != 0){
            return false;
        }
        unordered_map<char, char> map = {
            {')', '('},
            {'}', '{'},
            {']', '['}
        };
        for(int i = 0; i != s.size(); i++){
            if(map.count(s[i])){
                if(stk.empty() || stk.top() != map[s[i]]){
                    return false;
                }
                stk.pop();
            }else{
                stk.push(s[i]);
            }
        }
        if(stk.size() == 0){
            return true;
        }else{
            return false;
        }
    }

    bool ans2(string s){
        stack<char> stk;
        if(s.size() % 2 != 0){
            return false;
        }
        for(int i = 0; i != s.size(); i++){
            if(s[i] == '(' || s[i] == '[' || s[i] == '{'){
                stk.push(s[i]);
            }else{
                if(stk.empty()){
                    return false;
                }
                if(stk.top() != '(' && s[i] == ')'){
                    return false;
                }
                if(stk.top() != '[' && s[i] == ']'){
                    return false;
                }
                if(stk.top() != '{' && s[i] == '}'){
                    return false;
                }
                stk.pop();
            }
        }
        if(stk.size() == 0){
            return true;
        }else{
            return false;
        }
    }

};

void test1(){
    Solution s;
    string str = "()[]{}";
    bool ret = s.ans1(str);
    cout << ret << endl;
}



int main(void){
    test1();

    return 0;
}